Random numbers or bits are essential for virtually every cryptographic application. For example, seeds for key generation in both secret-key and public-key functions, session keys used for encryption and authentication, salts to be hashed with passwords, and challenges used in identification protocols are all assumed to be random by system designers. However, it is quite expensive to generate truly random numbers. Therefore, most applications rely on a cryptographic mechanism, known as a Pseudorandom Number Generator (“PRNG”), to generate numbers that approximate true random numbers-pseudorandom numbers.
A PRNG, defined in accordance with the relationship: G E=(K, G), includes an iterative process which consists of two functions K and G. Each iteration is indicated by the subscript “i”. The seed generation function K takes as input a security parameter k and returns a key K and an initial state s0. For i≧1, the generation function or transformation G takes as input the key K, the current state si−n and an auxiliary input ti, and returns a PRNG output yi and the next state si. The output yi is a number, wherein collectively the numbers produced for each iteration “i” is a series of pseudorandom numbers. We refer to the length of the PRNG output in each iteration (the length of each number produced) as the block length of the PRNG which equals |yi|.
PRNGs may be based on a variety of cryptographic primitives. The two most commonly used cryptographic primitives are block ciphers and hash functions. A cipher is a function used for encrypting data. Generally, ciphers use a key (a variable that is combined in some way with the unencrypted data) and a transformation (a formula for combining the key with a string of data) to create a string of pseudorandom numbers. A block cipher is a cipher that breaks up a string of data into shorter strings of data or “blocks” and combines the key with each block to create blocks of pseudorandom numbers.
In contrast, hash functions are functions that take strings of data of any length and return a string of data of some fixed length. Hash functions, when used for pseudorandom number generation, must fulfill certain requirements. The hash function must be hard to invert or “one-way.” This means that given the output of the hash function it is computationally infeasible to determine the input data. Additionally, the hash function must be collision intractable. This means that the hash function is a function for which it is computationally infeasible to find any two strings of data that transform to the same output string of data. Additionally, the hash function should be deterministic. This means that no matter how many times the exact same string of data is given, the hash function should produce the exact same output string of data.
One example of a PRNG that uses a block cipher as the underlying primitive is the ANSI X9.17 PRNG (the “ANSI PRNG”) as described in ANSI X9.17 (Revised), “American National Standard for Financial Institution Key Management (Wholesale),” America Bankers Association 1985 (hereby incorporated by reference herein). The ANSI PRNG is part of a popular baking standard and was suggested as, a mechanism to generate DES (Data Encryption Standard) keys and nonces. The ANSI PRNG, as defined according to the relationship G EFANSI=(KANSI,GANSI), is based on a block cipher F. FIG. 1 depicts the transformation GANSI 10. KANSI (not shown), generates key K and the current state Asi−1. The key K is used to key the block cipher F, thereby specifying a keyed block cipher FK 12. GANSI 10 uses the block cipher FK 12, the current state Asi−1 and an auxiliary input ti to produce the ANSI PRNG output Ayi and the next state Asi wherein Ayi=FK(Asi−1⊕FK(ti)) and Asi=FK(Ayi⊕FK(ti)), and wherein “⊕” is an exclusive-or operator.
One example of a PRNG that uses a hash function as the underlying primitive is the FIPS 186 PRNG (the “FIPS PRNG”), as described in FIPS PUB 186-2, (Change Notice 1), “Digital Signature Standard,” National Institute of Standards and Technologies, 2001 (hereby incorporated by reference herein). The FIPS PRNG was standardized for generating randomness in DSA (Digital Signature Algorithm). The FIPS PRNG, as defined according to the relationship G EHFIPS=(KFIPS, GFIPS), is based on a hash function H. FIG. 2 depicts the transformation GFIPS 30. KFIPS (not shown), generates key K and the current state Fsi−1. The key K is used to key the hash function H, thereby specifying a keyed hash function HK 32 GFIPS 30 uses the hash function HK 32 current state Fsi−1, and auxiliary input ti to produce the FIPS PRNG output Fyi and the next state Fsi, wherein Fyi=HK((Fsi−1+ti)mod 2n) and si=(si−1+yi+1)mod 2n, and wherein “” 34 is the operator (a+b)mod 2n (where a and b are inputs to the operator).
A particularly desirable property of PRNGs is forward security. Forward security has been applied to a range of cryptographic problems. A PRNG is said to be forward secure if the compromise of the current state si and key K does not enable an attacker to efficiently distinguishing any previously generated output from a truly random sequence of numbers. The ANSI PRNG is clearly not forward secure, because revealing the key K makes the underlying function (the seeded block cipher) FK, and hence the PRNG, completely reversible. In addition, the FIPS PRNG is also not forward secure because if the current state Fsi−1 and the output yi are known, every previous state, going back to the initial state can be determined.
It is common practice to model a PRNG as an iterative process. In each iteration “i”, a state (si−1) is input and a random number is output (the PRNG output yi) along with the next state (si). All states are assumed to be hidden at all times. Although such a model may seem sufficient for theoretical PRNGs, it does not capture all the nuances of a PRNG as it is used in practice. For example, some of the existing models do not model auxiliary inputs such as time stamps or counters that an attacker may be able to control. Furthermore, some state information may be leaked out over time or modified by a user or attacker.
One known method of making a forward secure PRNG out of any generic PRNG based on pseudorandom functions, was suggested by M. Bellare and B. Yee in “Forward Security in Private-Key Cryptography,” Cryptology ePrint Archive, Report 2001/035. In general, the disclosed method involves keeping part of the PRNG output secret and using this output to generate a new state and a key for each iteration. Because this known method was targeted for generic PRNGs, it does not necessarily yield the most efficient solution for any specific PRNG (such as the ANSI and FIPS PRNGs). In particular, this known method of creating forward secure PRNGs requires “re-keying” the block cipher for each PRNG iteration, which is an expensive and possibly unnecessary operation. Additionally, the model of PRNGs for which this method is suggested, does not consider auxiliary inputs, which are present in the ANSI and FIPS PRNGs. Auxiliary inputs (such as: keystrokes made by a user, the output of a clock or timer, a timestamp, samples from a low entropy source or other such inputs) are a common feature in practical PRNGs since they are a method of injecting something random into the PRNG at regular intervals and to prevent repeated seeds (keys and initial states) from causing repeated outputs.